/*!
 * FileName: luogu-USACO09OCT.cpp
 * This Problem is on luogu. The ID of the problem is USACO09OCT. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;
const int _N = 2510;
const int _M = 6210;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
struct node{
	int node;
	int w; 
	int nxt;
}edge[_M];
int head[_N];
int tot = 0;
void add(int u, int v, int w)
{
	edge[++tot].nxt = head[u];
	edge[tot].w = w;
	edge[tot].node = v;
	head[u] = tot;
	
	swap(u, v);
	
	edge[++tot].nxt = head[u];
	edge[tot].w = w;
	edge[tot].node = v;
	head[u] = tot;
} 
int dis[_N];
priority_queue<pair<int, int>,vector<pair<int, int > >, greater<pair<int, int> > > Q;
bool vis[_N];
void dijstra(int s, int t)
{
	memset(dis, 0x7f, sizeof(dis));
	memset(vis, false, sizeof(vis));
	dis[s] = 0;
	Q.push(make_pair(0, s));
	while(!Q.empty())
	{
		int now = Q.front().second;
		Q.pop();
		if(vis[now]) continue;
		vis[now] = true;
		for(register int i = head[now];i != 0;i = edge[i].nxt)
		{
			
		}
	}
}
int main()
{
    return 0;
}

